#include <cstdio>
#include <cstring>

const int INT_MAX = 0x7fffffff;
const int MAXN=2010;
const int MAXM=5000000;
struct edge
{
    int v,next,val;
};
edge e[MAXM];
int p[MAXN],eid;
int h[MAXN],gap[MAXN],source,sink;
inline void insert(int from,int to,int val)
{
    e[eid].v=to;
    e[eid].val=val;
    e[eid].next=p[from];
    p[from]=eid++;

    e[eid].v=from;
    e[eid].val=0;
    e[eid].next=p[to];
    p[to]=eid++;    
}
inline int dfs(int pos,int cost,int cnt)
{
    if (pos==sink) return cost;
    int j,minh=cnt-1,lv=cost,d;
    for (j=p[pos];j!=-1;j=e[j].next)
    {
        int v=e[j].v,val=e[j].val;
        if (val>0)
        {
            if (h[v]+1==h[pos])
            {
                if (lv<e[j].val) d=lv;
                else d=e[j].val;
                d=dfs(v,d,cnt);
                e[j].val-=d;
                e[j^1].val+=d;
                lv-=d;
                if (h[source]>=cnt) return cost-lv;
                if (lv==0) break;
            }
            if (h[v]<minh) minh=h[v];
        }
    }
    if (lv==cost)
    {
        --gap[h[pos]];
        if (gap[h[pos]]==0) h[source]=cnt;
        h[pos]=minh+1;
        ++gap[h[pos]];
    }
    return cost-lv;
}
int sap(int st,int ed,int cnt)
{
    source=st;
    sink=ed;
    int ret=0;
    memset(gap,0,sizeof(gap));
    memset(h,0,sizeof(h));
    gap[st]=cnt;
    while (h[st]<cnt)
        ret+=dfs(st,INT_MAX,cnt);
    return ret;
}

int sa[ MAXN ];

int main( )
{
    int t, i, j, sum, n, b;
    scanf("%d", &t);
    while ( t-- )
    {
        eid = 0;
        memset( p, -1, sizeof( p ) );
        sum = 0;
        scanf("%d", &n);
        memset( sa, 0, sizeof( sa ) );
        for ( i = 0; i < n; i++ )
        {
            for ( j = 0; j < n; j++ )
            {
                scanf("%d", &b);
                insert( i + 1, j + 1, b );
                sa[ j ] += b;
                sum += b;
            }
        }
        for ( i = 0; i < n; i++ )
        {
            scanf("%d", &b);
            insert( 0, i + 1, b );
            insert( i + 1, n + 1, sa[ i ] );
        }
        printf("%d\n", sum - sap( 0, n + 1, n + 2 ));
    }
    return 0;
}
